题解 P5072@洛谷【[Ynoi2015]盼君勿忘】

给定一个序列，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $s\bmod{p}$ 的结果。

乍一看好像不太可做，仔细分析发现有点规律：

在一个长度为 $a$ 的序列中，一个数出现次数为 $b$ 。则有 $2^{a-b}$ 个子序列不包含该元素，它的贡献是 $2^a-2^{a-b}$ 。

问题转化为如何快速求出每一个数的贡献值。

$10^5$ 、离线、维护数列，想到什么？莫队！

我们使用莫队记录双向链表（建议手写），维护每个数分别的出现次数，下标表示数，内容为出现次数。则这个链表的元素个数大致在 $\sqrt{n}$ 级别。在跳到当前区间后，枚举维护的链表，对于每个元素分别算出贡献值后相加即可。

还剩下最后一个问题：如何快速求出 $2^k$ ？普通的快速幂可能做不到，因为带一只 $\log$ ，容易被卡。果断选用光速幂。

光速幂是什么呢？就是一种 $\mathcal{O(\sqrt{n})}$ 预处理、 $\mathcal{O(1)}$ 查询的，求特定底数的幂的快速方法。具体方案是：预处理 $2^1,2^2,\cdots,2^{\sqrt{n}}$ 和 $2^{\sqrt{n}},2^{2\times\sqrt{n}},\cdots,2^n$ ，然后根据商和余数即可 $\mathcal{O(1)}$ 求出结果。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5;

ll n, m, a[N], SIZE, cnt[N], s[N], ans[N];
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Query {
	ll l, r, p, id;
	Query(ll a=0, ll b=0, ll c=0, ll d=0) : l(a), r(b), p(c), id(d) {}
	~Query() {}
	friend bool operator < (const Query &a, const Query &b) {
		ll x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];
struct myList {
	struct Node {
		ll pre, nxt;
		Node(ll a=0, ll b=0) : pre(a), nxt(b) {}
		~Node() {}
	}nd[N];
	ll tot;
	myList(ll a=0) : tot(a) {}
	~myList() {}
	void insert(ll x) {
		nd[tot].nxt = x;
		nd[x].pre = tot;
		tot = x;
	}
	void erase(ll x) {
		if(x != tot) {
			nd[nd[x].pre].nxt = nd[x].nxt;
			nd[nd[x].nxt].pre = nd[x].pre;
		}
		else {
			nd[nd[x].pre].nxt = 0;
			tot = nd[x].pre;
		}
		nd[x] = Node();
	}
}lst;
namespace qpow {
	ll pow1[N], pow2[N];
	void initPow(ll mod) {
		pow1[0] = pow2[0] = 1;
		for(ll i=1;i<=SIZE;i++) pow1[i] = pow1[i-1] * 2 % mod;
		for(ll i=1;i<=SIZE;i++) pow2[i] = pow2[i-1] * pow1[SIZE] % mod;
	}
	ll calc(ll x, ll mod) {return pow1[x%SIZE]*pow2[x/SIZE]%mod;}
}
void upd(ll x, ll k) {
	if(!(s[cnt[a[x]]]-=a[x])) lst.erase(cnt[a[x]]);
	if(!s[cnt[a[x]]+=k]) lst.insert(cnt[a[x]]);
	s[cnt[a[x]]] += a[x];
}

int main() {
	scanf("%lld%lld", &n, &m);
	SIZE = sqrt(n);
	for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
	for(ll i=1;i<=m;i++) scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].p), q[i].id = i;
	sort(q+1, q+1+m);
	ll l = 1, r = 0;
	for(ll i=1;i<=m;i++) {
//		printf("QUERY #%d: id=%d l=%d r=%d p=%d\n", i, q[i].id, q[i].l, q[i].r, q[i].p);
		qpow::initPow(q[i].p);
		while(l > q[i].l) upd(--l, 1);
		while(r < q[i].r) upd(++r, 1);
		while(l < q[i].l) upd(l++, -1);
		while(r > q[i].r) upd(r--, -1);
		for(ll j=lst.nd[0].nxt;j;j=lst.nd[j].nxt) {
//			printf("LIST POSITION: %d\n", j);
			ll _1 = qpow::calc(r-l+1, q[i].p);
			ll _2 = qpow::calc(r-l+1-j, q[i].p);
			ll _3 = ((_1 - _2) * s[j] + q[i].p) % q[i].p;
			ans[q[i].id] = (ans[q[i].id] + _3 + q[i].p) % q[i].p;
		}
	}
	for(ll i=1;i<=m;i++) printf("%lld\n", ans[i]);
	return 0;
}